class Solution {
public:
    string intToRoman(int num) {
        vector<int> hash = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector<string> ans = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        
        string ret;
        
        for(int i = 0;i < hash.size() && num > 0;){
            if(num >= hash[i]){
                num -= hash[i];
                ret += ans[i];
            }else{
                i++;
            }
        }
        return ret;
    }
};
